package com.leetcode.partition2;

import java.util.*;

/**
 * @author `RKC`
 * @date 2021/10/8 9:09
 */
public class LC187重复的DNA序列 {

    private static final int N = (int) (1e5 + 1), prime = 13331;
    private static long[] prefix = new long[N], hash = new long[N];

    public static List<String> findRepeatedDnaSequences(String s) {
        stringHash(s);
        Map<Long, Integer> map = new HashMap<>();
        List<String> answer = new ArrayList<>();
        for (int i = 1; i + 10 - 1 <= s.length(); i++) {
            int j = i + 10 - 1;
            //得到子串[i,j]的哈希值
            long h = substringHash(i, j);
            int count = map.getOrDefault(h, 0);
            if (count == 1) answer.add(s.substring(i - 1, j));
            map.put(h, count + 1);
        }
        return answer;
    }

    public static void main(String[] args) {
//        String s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT";
        String s = "AAAAAAAAAAA";
        System.out.println(findRepeatedDnaSequences(s));
    }

    private static long substringHash(int i, int j) {
        return hash[j] - hash[i - 1] * prefix[j - i + 1];
    }

    private static long stringHash(String s) {
        prefix[0] = 1;
        for (int i = 1; i <= s.length(); i++) {
            prefix[i] = prefix[i - 1] * prime;
            hash[i] = hash[i - 1] * prime + s.charAt(i - 1);
        }
        return hash[s.length()];
    }

    private static List<String> slidingWindow(String s) {
        //set存放结果用于去重，返回时转成list
        Set<String> answers = new HashSet<>();
        //存放10个子串是否有出现过
        Set<String> dnaSequences = new HashSet<>();
        for (int i = 0; i + 10 <= s.length(); i++) {
            //每10个字符为一组进行检查
            String dnaSequence = s.substring(i, i + 10);
            if (!dnaSequences.contains(dnaSequence)) {
                dnaSequences.add(dnaSequence);
                continue;
            }
            //当前序列已经在之前出现过
            answers.add(dnaSequence);
        }
        return new ArrayList<>(answers);
    }
}
